/// @tags: EulerCiruit
#include <cctype>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>

int const N = 1e3 + 5, M = 2e3 + 5, inf = 0x3f3f3f3f;

template <typename T>
inline T &read(T &x) {
  x = 0;
  bool f = false;
  short ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = true;
    ch = getchar();
  }
  while (isdigit(ch)) x = x * 10 + (ch ^ '0'), ch = getchar();
  if (f) x = -x;
  return x;
}

struct Edge {
  int v, nxt, f;
} e[M << 1];

int n, m, T, s, t, e_cnt = 1;
int cur[N], heads[N], h[N], deg[N], id[M], u[M], v[M];
std::vector<int> vec[N];
std::queue<int> q;

inline void add(int u, int v, int f) {
  e[++e_cnt].v = v, e[e_cnt].nxt = heads[u], heads[u] = e_cnt, e[e_cnt].f = f;
  e[++e_cnt].v = u, e[e_cnt].nxt = heads[v], heads[v] = e_cnt, e[e_cnt].f = 0;
}

inline bool bfs() {
	memset(h, 0, sizeof(h));
	while (q.size()) q.pop();
	h[s] = 1;
	q.push(s);
	while (q.size()) {
		int x = q.front();
		q.pop();
		for (int i = heads[x]; i; i = e[i].nxt) {
			Edge &edge = e[i];
			if (edge.f && !h[edge.v]) {
				q.push(edge.v);
				h[edge.v] = h[x] + 1;
				if (edge.v == t) return true;
			}
		}
	}
	return false;
}

int dinic(int x, int flow) {
	if (x == t) return flow;
	int rest = flow, k = 0;
	for (int i = heads[x]; i && rest; i = e[i].nxt) {
		if (e[i].f && h[e[i].v] == h[x] + 1) {
			k = dinic(e[i].v, std::min(e[i].f, rest));
			if (!k) h[e[i].v] = 0;
			e[i].f -= k;
			e[i ^ 1].f += k;
			rest -= k;
		}
	}
	return flow - rest;
}

inline bool build() {
  for (int i = 1; i <= n; ++i) {
    if (deg[i] & 1) return false;
    deg[i] /= 2;
    if (deg[i] > 0) add(s, i, deg[i]);
    if (deg[i] < 0) add(i, t, -deg[i]);
  }
  return true;
}

void geteuler(int u) {
  while (!vec[u].empty()) {
    int v = vec[u].back();
    vec[u].pop_back();
    geteuler(v);
    printf("%d ", u);
  }
}

inline void solve() {
  memset(heads, 0, sizeof(heads));
  memset(deg, 0, sizeof(deg));
  memset(id, 0, sizeof(id));
  e_cnt = 1;
  s = 0, t = read(n) + 1, read(m);
  for (int i = 0; i <= n + 1; ++i) vec[i].clear();
  char typ[2];
  for (int i = 1; i <= m; ++i) {
    read(u[i]), read(v[i]);
    scanf("%s", typ);
    deg[u[i]]--, deg[v[i]]++;
    if (typ[0] == 'U') id[i] = e_cnt + 1, add(v[i], u[i], 1);
  }
  if (!build()) return puts("No euler circuit exist"), void();
  while (bfs()) { dinic(s, inf); }
  for (int i = heads[s]; i; i = e[i].nxt) {
    if (e[i].f != 0) return puts("No euler circuit exist"), void();
  }
  for (int i = 1; i <= m; ++i) {
    if (id[i] && !e[id[i]].f) vec[u[i]].push_back(v[i]);  //把所有边反过来，输出就是正的了
    else
      vec[v[i]].push_back(u[i]);
  }
  printf("1 ");
  geteuler(1);
  putchar('\n');
}

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen("/tmp/CodeTmp/testdata.in", "r", stdin);
  freopen("/tmp/CodeTmp/testdata.out", "w", stdout);
#else
  freopen("EulerCircuit.in", "r", stdin);
  freopen("EulerCircuit.out", "w", stdout);
#endif
#endif

  read(T);
  while (T--) {
    solve();
    putchar('\n');
  }
  return 0;
}